package com.kobe.game_20;

/**
 * 
 * Starting in the top left corner of a 2×2 grid, there are 6 routes (without
 * backtracking) to the bottom right corner.
 * 
 * How many routes are there through a 20×20 grid?
 * 
 * 
 */
public class Game15 {
    public static void main(String[] args) {
        int size = 20;

        long[][] grid = new long[size + 1][size + 1];
        grid[0][0] = 1L;

        for (int i = 0; i <= size; i++) {
            for (int j = 0; j <= size; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }
                // top
                if (i == 0 && j > 0) {
                    grid[i][j] = 1L;
                }
                // left
                else if (j == 0 && i > 0) {
                    grid[i][j] = 1L;
                } else {
                    grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
                }
            }
        }

        System.out.println(grid[size][size]);

    }
}
